package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2022/2/11.<br><br>
 *
 * 中等：除自身以外数组的乘积
 */
public class Topic238 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        int[] array = new int[] {1,2,3,4};
        Util.printArray(solution.productExceptSelf(array));

        array = new int[] {-1,1,0,-3,3};
        Util.printArray(solution.productExceptSelf(array));
    }

    private interface BaseSolution {
        int[] productExceptSelf(int[] nums);
    }

    private static class Solution1 implements BaseSolution {

        @Override
        public int[] productExceptSelf(int[] nums) {
            int[] left = new int[nums.length];
            int[] right = new int[nums.length];

            left[0] = 1;
            for(int i = 1; i < nums.length; i++) {
                left[i] = nums[i - 1] * left[i - 1];
            }

            right[nums.length - 1] = 1;
            for(int i = nums.length - 2; i >= 0; i--) {
                right[i] = nums[i + 1] * right[i + 1];
            }

            for(int i = 0; i < nums.length; i++) {
                left[i] *= right[i];
            }
            return left;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int[] productExceptSelf(int[] nums) {
            int[] left = new int[nums.length];

            left[0] = 1;
            for(int i = 1; i < nums.length; i++) {
                left[i] = nums[i - 1] * left[i - 1];
            }

            int temp = nums[nums.length - 1];
            for(int i = nums.length - 2; i >= 0; i--) {
                left[i] = temp * left[i];
                temp *= nums[i];
            }
            return left;
        }
    }

}
